package org.sample.algorithm.sort;

public class MergeSort {

    public static int[] sort(int[] array) {
        merge(array, 0, array.length - 1, new int[array.length]);
        return array;
    }

    private static void merge(int array[], int low, int high, int temp[]) {
        if (low < high) {
            int mid = (low + high) >> 1;
            merge(array, low, mid, temp);
            merge(array, mid + 1, high, temp);
            mergeUnit(array, low, mid, high, temp);
        }
    }

    private static void mergeUnit(int array[], int low, int mid, int high, int temp[]) {
        int i = low, j = mid + 1;
        int m = mid, n = high;
        int k = 0;

        while (i <= m && j <= n) {
            if (array[i] <= array[j])
                temp[k++] = array[i++];
            else
                temp[k++] = array[j++];
        }

        while (i <= m)
            temp[k++] = array[i++];

        while (j <= n)
            temp[k++] = array[j++];

        System.arraycopy(temp, 0, array, low, k);
    }
}